This invention pertains to backup data and more particularly to a technique to speed up backup operations.
The task of quickly and efficiently backing up modern file storage systems is becoming more and more difficult, especially given the relentless increases in storage capacities along stratospheric growth curves. Storage hardware manufacturers now routinely produce compact, affordable rack-mounted systems sporting hundreds of gigabytes or even several terabytes. Software products make it equally routine to wrap the entire contents of such a system inside a single volume if so desired, supporting literally billions of individual files while maintaining high availability and failure recovery times for such a volume.
Backup technology has not even come close to keeping up with this explosive growth in storage. In particular, all major backup vendors still basically rely on brute-force searches to discover which files have changed since the last time they were archived. These searches generally result in a huge amount of wasted time and effort. Statistically speaking, only 20% of a system""s files will likely have changed on any given day. What is worse, each and every file""s metadata (data about the file) block must be read into memory and examined to see if it needs backup. Not only does this require massive numbers of I/O and processor cycles that could otherwise go towards servicing file system requests from users, but about 80% of this effort will be a complete waste of time.
An even bigger problem than the massive inefficiency described above is time. More and more organizations are discovering that they can no longer back up changes made to their data in a 24-hour periodxe2x80x94there are too many files to search through, and too few hours in the day.
Normally, a backup agent performs a tree walk over the complete set of files in a volume. Each file thus encountered whose data or metadata bits (also called the file""s archive bits) were turned on is locked and its contents stored to tape. Once safely on tape, the backup agent turns off the file""s archive bits, unlocks it, and continues its tree walk.
As system administrators and users have discovered, this xe2x80x9cnormalxe2x80x9d approach to incremental backups has critical problems. The worst of these is that the time required to walk a volume""s file tree is proportional to the number of files present. This number can easily be in the billions in modem systems, and even the fastest processors and disk I/O systems will not be able to inspect all of a volume""s files in any given 24-hour period. As if that is not enough, arbitrarily long xe2x80x9cquietxe2x80x9d periods are possible during which the backup agent encounters nothing but unmodified files. The tape backup system cannot be kept busy during these potentially numerous and extended periods of time.
In fact, shoe-shining can occur during these quiet times due to the physical characteristics of tape drives. When the system runs out of data to write, the tape must be slowed and stopped, then rewound to a point significantly before the point of last write so that the tape can be brought up to streaming speed upon (eventual) receipt of the next write buffer. This back-and-forth motion over the tape heads reminds people of how shoes are buffed and polished. Shoe-shining only serves to wear down the tape head, strip oxide from the medium, and significantly reduce the overall backup throughput.
One alternative to the xe2x80x9cnormalxe2x80x9d approach is to utilize a Change Journal, as described for the Microsoft(copyright) Windows(copyright) 2000 operating system. (xe2x80x9cMicrosoftxe2x80x9d and xe2x80x9cWindowsxe2x80x9d are registered trademarks of Microsoft Corporation in the United States and/or other countries.) In the article xe2x80x9cKeeping an Eye on Your NTFS Drives: The Windows 2000 Change Journal Explained,xe2x80x9d published in the Microsoft Systems Journal, September 1999, Jeffrey Cooperstein and Jeffrey Richter say that the Windows(copyright) 2000 Change Journal is xe2x80x9c . . . a database that contains a list of every change made to the files or directories on an NTFS 5.0 volume. Each volume has its own Change Journal database that contains records reflecting the changes occurring to that volume""s files and directories.xe2x80x9d
The Change Journal is implemented as a single, system-protected-and-maintained, fixed-maximum-size sparse file. Each time a file is changed in some way, an entry is appended to this special file. Change Journal entries include a 64-bit Update Sequence Number (USN), the file""s character string name, the time of the change, and the type of change that was made. Entries cannot span file blocks (typically 4K bytes), so some wasted space is possible per block. Entries are supposed to average about 100 bytes, but can be significantly larger if changed files have long pathnames. There may be multiple entries for any given file, as each change to the file is appended to the Change Journal as a separate record. Each change to a file requires not only that a distinct entry be added to the Change Journal, but that the file""s entry in the volume""s Master File Table (MFT) be persistently updated with that new entry""s USN. Change Journals are disabled by default on Windows(copyright) NT 5.0 volumes. All applications have equal access to a volume""s Change Journal, and any one of them may at any time enable or disable it. All records in the Change Journal are deleted each and every time it is disabled.
The Change Journal has several limitations. First, it is not guaranteed to be accurate (or even available) at any given point in time. Since it can be disabled at any time by any application (causing all its records to be purged), it cannot be relied upon for mission-critical applications such as backup. Second, enumerating all changed files will require a full scan through the Change Journal in which every changed file may contribute large numbers of entries. If only some of the entries in the Change Journal are to be used to back up files, processing time and memory must be wasted skipping over the irrelevant entries. Third, with a (conservative) estimate of 100 bytes per entry, memory and persistent storage overhead will be high. This problem is compounded by the fact that a single file may generate multiple entries, further lengthening the Change Journal. Fourth, each and every addition of a Change Journal record for a file will require that file""s entry in the Master File Table (MFT) be atomically and persistently updated (i.e., updated as a single transaction and retained even if the system should fail). Requiring atomic transactions should be avoided as much as possible, and the Change Journal requires an atomic transaction for each entry, regardless of the number of entries generated by a file. Finally, the Change Journal""s representation of file changes requires a large amount of memory.
U.S. Pat. No. 5,684,991 to Malcolm, issued Nov. 4, 1997, titled xe2x80x9cModification Metadata Set, Abstracted from Database Write Requests,xe2x80x9d describes another approach to speed up backup operations. According to Malcolm, whenever a write command is issued to write data to storage, a data set is added to a database identifying the subset of the file that was written. Where multiple data sets relate to the same area of a file, all but the most recent can be discarded. Where multiple data sets relate to contiguous areas of a file, they can be merged into a single data set. The database can then be used to simplify backup operations.
But the focus of Malcolm is to speed backup times by backing up only those parts of a file that have changed since the last backup operation. Malcolm may speed up backup operations, but recovering an archived file will generally be slower. To recreate a file from a tape, each separate archive operation must be scanned to determine whether any portion of the file is saved on that tape. Conceivably, recreating a file could require reading a segment of each tape. Second, Malcolm specifies no structure for the database that could improve performance. Without a structure specifically geared toward efficiency, inserting or deleting records can be time-consuming. Third, Malcolm provides no mechanism for ordering files for backup. Backup tools that must archive files in a particular order may be unable to use Malcolm. Fourth, Malcolm makes no provision for archiving files based on past checkpoints. Malcolm archives all files that have changed since the last archive operation, regardless of when the change occurred. Fifth, there is no robust and reliable provision to quickly identify the (usually relatively small) set of files that have changed since the last backup pass. Finally, Malcolm requires adding a data set to the database for each write command issued. Duplicates are eliminated through an optimization step.
Accordingly, a need remains for a system to identify files for backup that is always available, organizes the identified files in an easy way, and avoids repeatedly marking files for archiving.
When a volume is created, a Modified Files List (MFL) is established and an epoch timestamp (identifying an important point in time for the volume) is set. Whenever a file is first added to or changed on the volume, a corresponding entry is inserted in the MFL. Whenever a file is deleted from the volume and had a corresponding entry in the MFL, the corresponding entry is deleted. At any time, the epoch timestamp can be updated. An epoch timestamp earlier than the current epoch timestamp is selected for archiving purposes. The files inserted into the MFL before the selected epoch timestamp are enumerated and archived using a backup tool. After the backup tool turns off a file""s data and metadata archive bits, the corresponding entry is removed from the MFL.
The foregoing and other features, objects, and advantages of the invention will become more readily apparent from the following detailed description, which proceeds with reference to the accompanying drawings.